// 字符串相乘

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class solution_043 {
    public String multiply(String num1, String num2) {
        // 放入数组并赋值
        int[] arrays1 = new int[num1.length()];
        int[] arrays2 = new int[num2.length()];
        for (int i = 0; i < num1.length(); i++)
            arrays1[i] = num1.toCharArray()[i] - '0';
        for (int i = 0; i < num2.length(); i++)
            arrays2[i] = num2.toCharArray()[i] - '0';
        // 乘法
        List<int[]> multiply = new ArrayList<>();
        for (int i = 0; i < num2.length(); i++) {
            multiply.add(batchMultiply(arrays1, arrays2[i]));
        }
        // if (num2.length() == 1) {
        // for (int i : multiply.get(0))
        // result += i;
        // return result;
        // }

        // 加法
        List<int[]> addTwo = new ArrayList<>();
        if (multiply.size() == 1)
            addTwo.add(multiply.get(0));
        else {
            addTwo.add(batchAdd(multiply.get(1), multiply.get(0)));
            for (int i = 2; i < multiply.size(); i++) {
                addTwo.add(batchAdd(multiply.get(i), addTwo.get(0)));
                addTwo.remove(0);
            }
        }
        int[] add = addTwo.get(0);
        String result = "";
        int i = 0;

        for (i = 0; i < add.length; i++)
            if (add[i] != 0)
                break;
        for (; i < add.length; i++)
            result += add[i];
        return result == "" ? "0" : result;
    }

    public int[] batchMultiply(int[] array, int index) {
        int carry = 0;
        int[] result = new int[array.length + 1];
        for (int i = array.length - 1; i >= 0; i--) {
            result[i + 1] = (index * array[i] + carry) % 10;
            carry = (index * array[i] + carry) / 10;
        }
        result[0] = carry;
        return result;
    }

    public int[] batchAdd(int[] array1, int[] array2) {
        // array2需要乘10再相加
        // 两个数组大小应该是相同的
        int carry = 0;
        int length1 = array1.length;
        int length2 = array2.length;
        int[] result = new int[length2 + 2];
        result[length2 + 1] = array1[length1 - 1];
        int i, j;
        for (i = length1 - 2, j = length2 - 1; i >= 0 && j >= 0; i--, j--) {
            result[j + 1] = (array1[i] + array2[j] + carry) % 10;
            carry = (array1[i] + array2[j] + carry) / 10;
        }
        for (; j >= 0; j--) {
            result[j + 1] = (array2[j] + carry) % 10;
            carry = (array2[j] + carry) / 10;
        }
        result[0] = carry;
        return result;
    }

    // public static void main(String[] args) {
    // int[] array1 = new int[] { 1, 7, 3, 8 };
    // int[] array2 = new int[] { 9, 9, 9, 9, 9 };
    // for (int i : batchAdd(array1, array2))
    // System.out.println(i);
    // }
}

public class Solution043 {

}
